//
// Created by liushuai on 2021/1/1.
//

#include "merge.h"
//void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n){
//    int num_index1 = 0;
//    for(int index2=0;index2<n&&num_index1<(m+n);index2++){
//        while(nums1.at(num_index1)<=nums2.at(index2)&&nums1.at(num_index1)!=0)
//            num_index1+=1;
//        int start_move = num_index1+m;
//        if(nums1[start_move]==0&&start_move<(m+n)){
//            while(start_move>num_index1){
//                nums1[start_move] = nums1[start_move-1];
//                start_move--;
//            }
//            nums1[start_move] = nums2.at(index2);
//            num_index1++;
//        }
//        else{
//            nums1[num_index1] = nums2.at(index2);
//            num_index1++;
//        }
//
//    }
//}
//void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n){
//    std::vector<int>cache(nums1.begin(),nums1.begin()+m);
//    int index1 = 0;
//    int index2 = 0;
//    for(;index2<n;index2++){
//        while(cache[index1]<=nums2[index2]&&index1<m){
//            if(index1+index2<m+n){
//                nums1[index1+index2] = cache[index1];
//                index1++;
//            }
//
//        }
//            nums1[index1+index2] = nums2[index2];
//    }
//    while (index1<n){
//        nums1[index1+index2]=cache[index1];
//        index1++;
//    }
//}
void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n){
    int index1 = m-1,index2 = n-1;
    int lastElem = m+n-1;
    while(index1>=0||index2>=0){
        if(nums1[index1]>nums2[index2]){
            nums1[lastElem] = nums1[index1];
            index1--;
            lastElem--;
        }else{
            nums1[lastElem] = nums2[index2];
            index2--;
            lastElem--;
        }
    }
}